#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"

typedef char BTDatatype;
typedef struct BTNode
{
	BTDatatype x;
	struct BTNode* left;
	struct BTNode* right;
}BTNode;

void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	InOrder(root->left);
	printf("%c ", root->x);
	InOrder(root->right);
}


BTNode* BTFindNode(BTNode* root, BTDatatype n)
{
	if (root == NULL)
	{
		return NULL;
	}

	if (root->x == n)
	{
		return root;
	}

	BTNode* left = BTFindNode(root->left, n);
	if (left)
	{
		return left;
	}

	BTNode* right = BTFindNode(root->right, n);
	if (right)
	{
		return right;
	}
	return NULL;
}

BTNode* BTCreate(BTDatatype* a, int* pi)
{
	if (a[*pi]=='#')
	{
		(*pi)++;
		return NULL;
	}

	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
	root->x = a[(*pi)++];
	root->left = BTCreate(a, pi);
	root->right = BTCreate(a, pi);
	return root;
}

void LevelOrder(BTNode* root)
{
	Queue queue;
	QueueInit(&queue);
	QueuePush(&queue, root->x);
	while (!QueueEmpty(&queue))
	{
		BTDatatype x = QueueFront(&queue);
		printf("%c ", x);
		QueuePop(&queue);
		BTNode* goal = BTFindNode(root, x);
		if (goal->left != NULL)
		{
			QueuePush(&queue, goal->left->x);
		}

		if (goal->right != NULL)
		{
			QueuePush(&queue, goal->right->x);
		}
	}
}

int main()
{
	char a[] = "abc##de#g##f###";
	int i = 0;
	BTNode* root = BTCreate(a, &i);
	InOrder(root);
	printf("\n");
	LevelOrder(root);
	return 0;
}


